// 200.[BFS广搜法] 岛屿数量
// https://leetcode.cn/problems/number-of-islands/
// 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为
// 11，则将其加入队列，
// 开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11
// 都会被重新标记为 00。
// 直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。
#include <bits/stdc++.h>
using namespace std;

class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0';
          queue<pair<int, int>> neighbors;
          neighbors.push({r, c});
          while (!neighbors.empty()) {
            auto rc = neighbors.front();
            neighbors.pop();
            int row = rc.first, col = rc.second;
            if (row - 1 >= 0 && grid[row - 1][col] == '1') {
              neighbors.push({row - 1, col});
              grid[row - 1][col] = '0';
            }
            if (row + 1 < nr && grid[row + 1][col] == '1') {
              neighbors.push({row + 1, col});
              grid[row + 1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col - 1] == '1') {
              neighbors.push({row, col - 1});
              grid[row][col - 1] = '0';
            }
            if (col + 1 < nc && grid[row][col + 1] == '1') {
              neighbors.push({row, col + 1});
              grid[row][col + 1] = '0';
            }
          }
        }
      }
    }
    return num_islands;
  }
};
